'''
https://leetcode.cn/problems/decrease-elements-to-make-array-zigzag/
'''
from typing import List


class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        n = len(nums)
        res1 = 0
        for i in range(0, n, 2):
            left = nums[i-1] if i > 0 else float('inf')
            right = nums[i+1] if i < n-1 else float('inf')
            minv = min(left, right)
            if nums[i] >= minv:
                res1 += nums[i] - minv + 1
        res2 = 0
        for i in range(1, n, 2):
            left = nums[i-1] if i > 0 else float('inf')
            right = nums[i+1] if i < n-1 else float('inf')
            minv = min(left, right)
            if nums[i] >= minv:
                res2 += nums[i] - minv + 1
        return min(res1, res2)
